1658. 将 x 减到 0 的最小操作数

Similar Question

Solution Tips

方案一: 记忆化递归

var minOperations = function(nums, x) {
    // 回溯法, 暴力处理, 每次都有2种选择, 移除一个头, 移除一个尾
    // 滑动窗口? 怎么处理的? 贪心? 先删除最大的? 感觉没道理的
    // 其实是 x 数之和? 从头尾找连续的构成 target ? 但是我的记忆中, 对撞指针需要是有序的
    // 赶紧开始回溯吧, 不然都做不出来了
    let res = Number.MAX_SAFE_INTEGER;
    const map = {};
    recursive(0, nums.length - 1, x, 0);
    // 先减头, 后减尾, 以及先减去尾, 再减去头, 其实是一样的
    // 记忆化递归还是超时了, 要从记忆化递归去思考如何优化

    return res === Number.MAX_SAFE_INTEGER ? -1 : res;

    function recursive(start, end, target, op) {
        // 从 rest 的头尾中选一个, 继续递归
        if (target === 0) {
            res = Math.min(res, op)
            return;
        }

        // nums[i] 均为正数
        if (target < 0) {
            return;
        }

        if (start > end) {
            return;
        }

        // 如果有值, 就可以直接 return
        if (map[`${start}-${end}-${target}`]) {
            return;
        }

        map[`${start}-${end}-${target}`] = true;

        recursive(start + 1, end, target - nums[start], op + 1);
        recursive(start, end - 1, target - nums[end], op + 1);
    }
}

方案二: 反向思维 + 滑动窗口

边界条件太多了, 完全无法判断 start 和 end 到底什么时候该结束

这个时候的惯例就是加上一个 哨兵? 不行, 如果加 0 的话不影响 subSum 但是会会影响 end - start

官解其实也是单个滑动窗口, 不如我的好理解

var minOperations = function(nums, x) {
    const sum = nums.reduce((acc, val) => acc + val, 0);
    const target = sum - x;

    if (target === 0) {
        return nums.length;
    }


    let maxCount = 0;
    let subSum = 0;
    let left = 0;
    let right = 0;
    while (left <= right && right < nums.length) {

        while (subSum < target) {
            subSum += nums[right];
            right++;
        }

        // 大于等于的瞬间
        while (subSum >= target) {
            if (subSum === target) {
                maxCount = Math.max(maxCount, right - left);
                subSum -= nums[left];
                left++;
            }
            if (subSum > target) {
                subSum -= nums[left];
                left++;
            }
        }
    }

    let res = nums.length - maxCount;

    return res === nums.length ? -1 : res;
};
let nums = [5,1,4,2,3], x = 6
console.log(minOperations(nums, x))